package demo.practice.leetcode;


import java.util.LinkedList;

public class Offer54 {

    public static void main(String[] args) {
        Offer54 o= new Offer54();
        TreeNode r= new TreeNode(3);
        r.left= new TreeNode(1);
        r.right= new TreeNode(4);
        r.left.right= new TreeNode(2);

        TreeNode n = new TreeNode(5);
        n.left= new TreeNode(3);
        n.right= new TreeNode(6);
        n.left.right= new TreeNode(4);
        n.left.left= new TreeNode(2);
        n.left.left.left= new TreeNode(1);

        TreeNode e = new TreeNode(1);
        e.right= new TreeNode(2);

        int a=o.kthLargest(e,2);
        System.out.println(a);

    }

    LinkedList<Integer> list= new LinkedList<>();

    public int kthLargest(TreeNode root, int k) {
        foreach( root,  k);
        return list.get(k-1);
    }

    private void foreach(TreeNode root, int k) {//前序遍历插入到list中
        if(root!=null){
            add(root.val,k);
            if (root.right!=null){
                foreach(root.right,  k);
            }
            if (root.left!=null){
                foreach(root.left,  k);
            }
        }
    }

    private void add(Integer val, int k){
        if(list.size()==0){
            list.add(val);
            return;
        }
        for(int i=0;i<list.size();i++){
            if(val<list.get(i)){ //如果value更小，就往后移动
                if(i==list.size()-1 && list.size()<k)//到最后也没插入，就放到最后了
                {
                    list.add(val);
                    break;
                }
                //continue;
            }else{
                list.add(i,val);//否则，插入到该位置
                if(list.size()>k)
                    list.remove(list.getLast());
                break;
            }
        }
    }

}
